package com.sgx.learning.luban.arithmetic.sort;

import java.util.Arrays;

public class QuickSort {

    public static void sort(int[] arr,int left,int right){
        int low = left;
        int high = right;
        int base = arr[low];
        while(low < high) {
            while(low <= high && arr[high] >= base) {
                high --;
            }
            if(low < high) {
                int temp = arr[high];
                arr[high] = arr[low];
                arr[low] = temp;
                low ++;
            }
            while(low < high && arr[low] <= base) {
                low++;
            }
            if(low < high) {
                int temp = arr[low];
                arr[low] = arr[high];
                arr[high] = temp;
                high --;
            }
        }

        if(low > left) {
            sort(arr,left,low - 1);
        }
        if(high < right) {
            sort(arr,low + 1,right);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,3,10,22,1};
        sort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
